package com.graph;

import java.util.LinkedList;

public class Solution1091 {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        int m = grid.length;
        int n = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        int res = 0;
        int[] cur = null;
        boolean[][] visited = new boolean[m][n];
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            for (int i = 0; i < size; i++) {
                cur = queue.removeFirst();
                if (cur[0] == m - 1 && cur[1] == n - 1 && grid[m - 1][n - 1] == 0) return res;
                if (cur[0] - 1 >= 0 && cur[1] - 1 >= 0 && !visited[cur[0] - 1][cur[1] - 1] && grid[cur[0] - 1][cur[1] - 1] == 0) {
                    queue.add(new int[]{cur[0] - 1, cur[1] - 1});
                    visited[cur[0] - 1][cur[1] - 1] = true;
                }
                if (cur[0] - 1 >= 0 && !visited[cur[0] - 1][cur[1]] && grid[cur[0] - 1][cur[1]] == 0) {
                    queue.add(new int[]{cur[0] - 1, cur[1]});
                    visited[cur[0] - 1][cur[1]] = true;
                }
                if (cur[0] - 1 >= 0 && cur[1] + 1 <= n - 1 && !visited[cur[0] - 1][cur[1] + 1] && grid[cur[0] - 1][cur[1] + 1] == 0) {
                    queue.add(new int[]{cur[0] - 1, cur[1] + 1});
                    visited[cur[0] - 1][cur[1] + 1] = true;
                }
                if (cur[1] + 1 <= n - 1 && !visited[cur[0]][cur[1] + 1] && grid[cur[0]][cur[1] + 1] == 0) {
                    queue.add(new int[]{cur[0], cur[1] + 1});
                    visited[cur[0]][cur[1] + 1] = true;
                }
                if (cur[0] + 1 <= m - 1 && cur[1] + 1 <= n - 1 && !visited[cur[0] + 1][cur[1] + 1] && grid[cur[0] + 1][cur[1] + 1] == 0) {
                    queue.add(new int[]{cur[0] + 1, cur[1] + 1});
                    visited[cur[0] + 1][cur[1] + 1] = true;
                }
                if (cur[0] + 1 <= m - 1 && !visited[cur[0] + 1][cur[1]] && grid[cur[0] + 1][cur[1]] == 0) {
                    queue.add(new int[]{cur[0] + 1, cur[1]});
                    visited[cur[0] + 1][cur[1]] = true;
                }
                if (cur[0] + 1 <= m - 1 && cur[1] - 1 >= 0 && !visited[cur[0] + 1][cur[1] - 1] && grid[cur[0] + 1][cur[1] - 1] == 0) {
                    queue.add(new int[]{cur[0] + 1, cur[1] - 1});
                    visited[cur[0] + 1][cur[1] - 1] = true;
                }
                if (cur[1] - 1 >= 0 && !visited[cur[0]][cur[1] - 1] && grid[cur[0]][cur[1] - 1] == 0) {
                    queue.add(new int[]{cur[0], cur[1] - 1});
                    visited[cur[0]][cur[1] - 1] = true;
                }
            }
        }
        return -1;
    }
}
